package com.acwing.partition2;

import java.io.*;
import java.util.ArrayList;
import java.util.List;

/**
 * @author `RKC`
 * @date 2021/12/11 15:03
 */
public class AC187导弹防御系统 {

    private static int answer = 0x3f3f3f3f;

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
        while (true) {
            String[] s = reader.readLine().split("\\s+");
            int n = Integer.parseInt(s[0]);
            if (n == 0) break;
            int[] heights = new int[n];
            s = reader.readLine().split("\\s+");
            for (int i = 0; i < n; i++) heights[i] = Integer.parseInt(s[i]);
            dfs(heights, new ArrayList<>(), new ArrayList<>(), 0, 0, 0);
            writer.write(answer + "\n");
            answer = 0x3f3f3f3f;
        }
        writer.flush();
    }

    private static void dfs(int[] heights, List<Integer> incr, List<Integer> decr, int incrMiss, int decrMiss, int index) {
        if (incrMiss + decrMiss >= answer) return;
        if (index == heights.length) {
            answer = Math.min(answer, incrMiss + decrMiss);
            return;
        }
        //维护一个递增的单调序列
        int height = heights[index], i = equalOrHigher(incr, height), missile = 0, temp = 0;
        if (incr.isEmpty() || (i == incr.size() - 1 && height > incr.get(incr.size() - 1))) {
            incr.add(height);
            missile = 1;
        } else if ((i >= 0 && i < incr.size() - 1) || i == incr.size() - 1) {
            temp = incr.get(i);
            incr.set(i, height);
        }
        dfs(heights, incr, decr, incrMiss + missile, decrMiss, index + 1);
        //回溯，如果是修改操作，进行现场恢复，如果是添加操作，进行删除，数组删除最后一个元素，时间复杂度O(1)
        if (missile == 0) incr.set(i, temp);
        else incr.remove(incr.size() - 1);
        //维护一个递减的单调序列
        i = equalOrLower(decr, height);
        missile = 0;
        if (decr.isEmpty() || (i == decr.size() - 1 && height < decr.get(decr.size() - 1))) {
            decr.add(height);
            missile = 1;
        } else if ((i >= 0 && i < decr.size() - 1) || i == decr.size() - 1) {
            temp = decr.get(i);
            decr.set(i, height);
        }
        dfs(heights, incr, decr, incrMiss, decrMiss + missile, index + 1);
        //集合属于引用传递，所以decr集合也需要根据状态进行回溯
        if (missile == 0) decr.set(i, temp);
        else decr.remove(decr.size() - 1);
    }

    private static int equalOrLower(List<Integer> nums, int target) {
        //nums是倒序的
        int left = 0, right = nums.size() - 1;
        while (left < right) {
            int mid = (left + right) >>> 1;
            if (nums.get(mid) > target) left = mid + 1;
            else right = mid;
        }
        return left;
    }

    private static int equalOrHigher(List<Integer> nums, int target) {
        //nums是正序的
        int left = 0, right = nums.size() - 1;
        while (left < right) {
            int mid = (left + right) >>> 1;
            if (nums.get(mid) >= target) right = mid;
            else left = mid + 1;
        }
        return left;
    }
}
